namespace tb
{
	template <typename T>
	TB_INLINE HashMap<T>::HashMap()
	{
		m_NodesFilled = 1;
		m_NodesMaximum = 4;
		m_Nodes = new BinaryLeaf*[m_NodesMaximum];
		for (unsigned int i = 0; i < m_NodesMaximum; i++)
		{
			m_Nodes[i] = new BinaryLeaf;
			m_Nodes[i]->index = i;
		}

		m_TreeRoot = m_Nodes[0];
	}

	template <typename T>
	TB_INLINE HashMap<T>::~HashMap()
	{

	}

	template <typename T>
	TB_INLINE HashMap<T>& HashMap<T>::Insert(const char* a_Key, T* a_Value)
	{
		_InsertKey(m_TreeRoot, (const KeyValue*)a_Key, 0, strlen(a_Key), a_Value);

		return *this;
	}

	template <typename T>
	TB_INLINE T* HashMap<T>::Find(const char* a_Key)
	{
		return _Find(m_TreeRoot, (const KeyValue*)a_Key, 0, strlen(a_Key));
	}

	// ================================
	// Functions
	// ================================

	template <typename T>
	TB_INLINE unsigned int HashMap<T>::_EmptyLeaf()
	{
		if (m_NodesFilled + 1 == m_NodesMaximum)
		{
			m_NodesMaximum *= 2;

			BinaryLeaf** temp_leaves = new BinaryLeaf*[m_NodesMaximum];
			for (unsigned int i = 0; i < m_NodesMaximum; i++)
			{
				temp_leaves[i] = new BinaryLeaf;
				temp_leaves[i]->index = i;
			}

			for (unsigned int i = 0; i < m_NodesFilled; i++)
			{
				memcpy(temp_leaves[i], m_Nodes[i], sizeof(BinaryLeaf));
			}

			delete [] m_Nodes;
			m_Nodes = temp_leaves;

			m_TreeRoot = m_Nodes[0];
		}

		return m_NodesFilled++;
	}

	template<typename T>
	TB_INLINE void HashMap<T>::_InsertKey(BinaryLeaf* a_Target, const KeyValue* a_Key, unsigned int a_Offset, unsigned int a_Length, T* a_Value)
	{
		BinaryLeaf* target = a_Target;

		if (a_Offset == a_Length) 
		{ 
			target->key_original = new char[a_Length + 1];
			memset(target->key_original, 0, a_Length + 1);
			strncpy(target->key_original, (const char*)a_Key, a_Length);

			target->value = a_Value;

			return;
		}

		const KeyValue* src = a_Key + a_Offset;

		if (target->index == 0 && target->key == 0)
		{
			m_Nodes[target->right]->key = *src;
			m_Nodes[target->right]->offset = a_Offset;

			return _InsertKey(target, a_Key, a_Offset + 1, a_Length, a_Value);
		}

		// no children yet

		if (!target->left)
		{
			if (target->key == *src && target->offset == a_Offset)
			{
				if (*(src + 1) == 0)
				{
					target->key_original = new char[a_Length + 1];
					memset(target->key_original, 0, a_Length + 1);
					strncpy(target->key_original, (const char*)a_Key, a_Length);

					target->value = a_Value;

					return; 
				}

				unsigned int newleaf = _EmptyLeaf();
				target = m_Nodes[target->index];
				target->left = newleaf;

				m_Nodes[target->left]->key = *(src + 1);
				m_Nodes[target->left]->offset = a_Offset + 1;
			}
			else
			{
				unsigned int newleaf = _EmptyLeaf();
				target = m_Nodes[target->index];
				target->left = newleaf;

				m_Nodes[target->left]->key = *src;
				m_Nodes[target->left]->offset = a_Offset;
			}

			return _InsertKey(m_Nodes[target->left], a_Key, a_Offset + 1, a_Length, a_Value);
		}
		else if (target->key == *src && m_Nodes[target->left]->key == *(src + 1))
		{
			return _InsertKey(m_Nodes[target->left], a_Key, a_Offset + 1, a_Length, a_Value);
		}

		// siblings

		if (!target->right)
		{
			unsigned int newleaf = _EmptyLeaf();
			target = m_Nodes[target->index];
			target->right = newleaf;

			m_Nodes[target->right]->key = *src;
			m_Nodes[target->right]->offset = a_Offset;

			return _InsertKey(m_Nodes[target->right], a_Key, a_Offset + 1, a_Length, a_Value);
		}
		else if (m_Nodes[target->right]->key == *(src + 1))
		{
			return _InsertKey(m_Nodes[target->right], a_Key, a_Offset + 1, a_Length, a_Value);
		}
		else // keep going right
		{
			if (
				m_Nodes[target->right]->left && 
				m_Nodes[m_Nodes[target->right]->left]->key == *(src + 1)
			)
			{
				return _InsertKey(m_Nodes[target->right], a_Key, a_Offset, a_Length, a_Value);
			}
			else
			{
				return _InsertKey(m_Nodes[target->right], a_Key, a_Offset, a_Length, a_Value);
			}
		}
	}

	template<typename T>
	TB_INLINE T* HashMap<T>::_Find(BinaryLeaf* a_Target, const KeyValue* a_Key, unsigned int a_Offset, unsigned int a_Length)
	{
		if (a_Target->offset + 1 == a_Length)
		{
			return a_Target->value;
		}

		const KeyValue* src = a_Key + a_Offset;

		BinaryLeaf* node_left = m_Nodes[a_Target->left];
		BinaryLeaf* node_right = m_Nodes[a_Target->right];

		if (a_Offset > 0)
		{
			if (node_left->key == *(src + 1))
			{
				return _Find(node_left, a_Key, a_Offset + 1, a_Length);
			}
			else if (a_Target->right)
			{
				return _Find(node_right, a_Key, a_Offset, a_Length);
			}
		}
		else
		{
			if (a_Target->key == *src && node_left->key == *(src + 1))
			{
				return _Find(node_left, a_Key, a_Offset + 1, a_Length);
			}
			else if (a_Target->right)
			{
				return _Find(node_right, a_Key, a_Offset, a_Length);
			}
		}

		return NULL;
	}


}